其問題如下:
給定n個數字 以及一個指定的和S,是否存在一些由0和1組成的a,使得
舉例來說,n=8,給定85, 13, 9, 7, 47, 27, 99, 86,S=172,則a=(1, 1, 0, 0, 1, 1, 0, 0)可以滿足其要求
在不對給定的數字多做假設的情況下,這種一般類型的背包問題是NP完備
也就是隨便給n個數字,要決定是否某些數字的和等於某個數字,沒有人能找到在多項式時間內完成的方法
可以看得出來要驗證a是否滿足要求很容易,但要能找到滿足要求的a相當困難
不過,在某些很特殊的情況下,解開背包問題是相當容易的
假設給定的數字為3, 6, 11, 25, 46, 95, 200, 411
其初始給定的數字為遞增,且每個數字要比前面數字總和來得大(例如:6比3大,11比3+6大...)
這種情況稱為超級遞增背包(superincreasning Knapsack)
可以透過以下函數檢查:
def check_superincreasing(W):
Ws = W.cumsum()
Ws = np.insert(Ws[:-1], 0, 0)
if (Ws < W).all():
return True
else: return False
check_superincreasing(np.array([3, 6, 11, 25, 46, 95, 200, 411]))
假設指定的和S=309,以下示範如何在多項式時間找出a:
def superincreasing(S, W):
if not check_superincreasing(W):
return ValueError('W not superincreasing')
else:
a = np.zeros(len(W))
for i in range(len(W)):
if S >= W[-i-1]:
a[-i-1] = 1
S -= W[-i-1]
if S != 0:
return 'a does not exist'
return a
superincreasing(309, np.array([3, 6, 11, 25, 46, 95, 200, 411]))
有了以上的知識,終於可以進入背包加密的主要演算法:
Bob先隨機地產生一個超級遞增背包W
並隨機地選擇一個比這個超級背包總和還要大的數q
以及一個比q還要小且互質的數r
這三個東西(W,q,r)就是Bob自己要收好的私鑰
將W內的所有數字乘以r除以q,所得到的餘數就是公鑰
舉個實際的例子:
Bob先隨機地生成超級遞增背包W = (114, 117, 238, 471, 944, 1891, 3777, 7553)
此背包總和為15105
隨機地選擇比15105大的整數q = 21888,同時也隨機找一個與q互質數字r = 20555
接著Bob將W內的東西都乘以r除以q取餘數,得到一般背包(1254, 19143, 11066, 6909, 11152, 18305, 21387, 331)
def transform_super2ordinary(q, r, W):
if np.gcd(q,r)!=1:
return ValueError('q,r must be coprime')
if not check_superincreasing(W):
return ValueError('W not superincreasing')
if q < W.sum():
return ValueError('q must be bigger')
else:
return (W * r) % q
q = 21888
r = 20555
W = np.array([114, 117, 238, 471, 944, 1891, 3777, 7553])
transform_super2ordinary(q, r, W)
一般人只能看到(1254, 19143, 11066, 6909, 11152, 18305, 21387, 331),完全不知道q, r, W的值
首先,要用Bob發布的公鑰進行加密,明文先以約定俗成的方式轉成二元方式表示:10010110,這個二進位就是背包問題的a,因此對應一般背包公鑰密文C即為1254x1+19143x0+11066x1+6909x0+11152x1+18305x1+21387x0=47855
對於Trudy來說,由於解和為47855,給定背包(1254, 19143, 11066, 6909, 11152, 18305, 21387, 331)的問題為NP完備,想在多項式時間內解出明文a幾乎不可能,因此攔截到47855對於解開明文沒有幫助
(當然範例只有8個數字只有256種可能一下就可以猜出來)
在收到47855後,Bob得先拿起手上的q和r做個小小計算
由於q和r互質的關係,根據某個有趣的性質,存在一個數字 使得
Bob可以叫出python輸入
pow(r, -1, q)
來找到
此時因為
1254xa1 + 19143xa2 + 11066xa3 + 6909xa4 + 11152xa5 + 18305xa6 + 21387xa7 + 331xa8 =
47855
這些公鑰都是從超級遞增背包成以r除以q而來
rx114xa1 + rx117xa2 + rx238xa3 + rx471xa4 + rx944xa5 + rx1891xa6 + rx3777xa7 + rx7553xa8 =
47855 mod q
在兩邊同乘剛剛找到的 ,因為 因此
114xa1 + 117xa2 + 238xa3 + 471xa4 + 944xa5 + 1891xa6 + 3777xa7 + 7553xa8 =
47855x = 6253 mod q
總而言之,Bob只需要拿手上的超級遞增背包解Alice傳來的密文乘以 後的新密文
由於解超級遞增背包相當簡單,因此
superincreasing(6253, W)
得到明文10010110
最後一點,雖然背包加密法是NP完備,Shamir(RSA的S,之後還會看到幾次這個厲害的人物)找到能夠在多項式時間內破解的方法
以上介紹的背包加密法有個問題,我們從超級遞增背包轉換至一般背包的方式,會讓生成出的背包不夠一般
Shamir利用生成出來不夠一般的特性破解,讓我們有很高的機率可以猜出a是多少
由於此一破解讓背包加密法蒙上陰影,即使後續有研發出更多安全版的背包加密,實務上也沒人使用
儘管如此,我們仍是可以從背包加密法身上學到不少公鑰設計上的巧思